Square packing

 ( Packing Problems ) 

Square packing is a packing problem where the objective is to determine how many congruent can be packed into some larger shape, often a square or circle.

---

In a square Square packing in a square is the problem of determining the maximum number of (squares of side length one) that can be packed inside a larger square of side length $a$. If $a$ is an integer, the answer is $a^2,$ but the precise – or even asymptotic – amount of unfilled space for an arbitrary non-integer $a$ is an open question.

The smallest value of $a$ that allows the packing of $n$ unit squares is known when $n$ is a perfect square (in which case it is $\backslash sqrt\{n\}$), as well as for $n=\{\}$2, 3, 5, 6, 7, 8, 10, 13, 14, 15, 24, 34, 35, 46, 47, and 48. For most of these numbers (with the exceptions only of 5 and 10), the packing is the natural one with axis-aligned squares, and $a$ is $\backslash lceil\backslash sqrt\{n\}\backslash ,\backslash rceil$, where $\backslash lceil\backslash ,\backslash \; \backslash rceil$ is the ceiling function (round up) function. The figure shows the optimal packings for 5 and 10 squares, the two smallest numbers of squares for which the optimal packing involves tilted squares.

The smallest unresolved case is $n=11$. It is known that 11 unit squares cannot be packed in a square of side length less than $\backslash textstyle\; 2+2\backslash sqrt\{4/5\}\; \backslash approx\; 3.789$. By contrast, the tightest known packing of 11 squares is inside a square of side length approximately 3.877084 found by Walter Trump.The 2000 version of listed this side length as 3.8772; the tighter bound stated here is from

The smallest case where the best known packing involves squares at three different angles is $n=17$. It was discovered in 1998 by John Bidwell, an undergraduate student at the University of Hawaiʻi, and has side length $a\backslash approx\; 4.6756$.

Below are the minimum solutions for values up to $n\; =\; 12$; the case $n=11$ remains unresolved:

1	1
2	2
3	2
4	2
5	2.707...	$2+\backslash frac\{\backslash sqrt\{2\}\}\{2\}$
6	3
7	3
8	3
9	3
10	3.707...	$3+\backslash frac\{\backslash sqrt\{2\}\}\{2\}$
11	3.877... ?
12	4

---

Asymptotic results For larger values of the side length $a$, the exact number of unit squares that can pack an $a\backslash times\; a$ square remains unknown. It is always possible to pack a $\backslash lfloor\; a\backslash rfloor\; \backslash !\backslash times\backslash !\; \backslash lfloor\; a\backslash rfloor$ grid of axis-aligned unit squares, but this may leave a large area, approximately $2a(a-\backslash lfloor\; a\backslash rfloor)$, uncovered and wasted. Instead, Paul Erdős and Ronald Graham showed that for a different packing by tilted unit squares, the wasted space could be significantly reduced to $o(a^\{7/11\})$ (here written in little o notation). Later, Graham and Fan Chung further reduced the wasted space to $O(a^\{3/5\})$. However, as Klaus Roth and Bob Vaughan proved, all solutions must waste space at least $\backslash Omega\backslash bigl(a^\{1/2\}(a-\backslash lfloor\; a\backslash rfloor)\backslash bigr)$. In particular, when $a$ is a half-integer, the wasted space is at least proportional to its square root. The precise asymptotic growth rate of the wasted space, even for half-integer side lengths, remains an open problem.

Some numbers of unit squares are never the optimal number in a packing. In particular, if a square of size $a\backslash times\; a$ allows the packing of $n^2-2$ unit squares, then it must be the case that $a\backslash ge\; n$ and that a packing of $n^2$ unit squares is also possible.

---

In a circle

Square packing in a circle is a related problem of packing n unit squares into a circle with radius as small as possible. For this problem, good solutions are known for n up to 35. Here are the minimum known solutions for up to $n\; =\; 12$ (although only the cases $n\; =\; 1$ and $n\; =\; 2$ are known to be optimal):

1	$\backslash sqrt\{2\}/2\; \backslash approx\; 0.707\backslash ldots$
2	$\backslash sqrt\{5\}/2\; \backslash approx\; 1.118\backslash ldots$
3	$5\backslash sqrt\{17\}/16\; \backslash approx\; 1.288\backslash ldots$
4	$\backslash sqrt\{2\}\; \backslash approx\; 1.414\backslash ldots$
5	$\backslash sqrt\{10\}/2\; \backslash approx\; 1.581\backslash ldots$
6	1.688...
7	$\backslash sqrt\{13\}/2\; \backslash approx\; 1.802\backslash ldots$
8	1.978...
9	$\backslash sqrt\{1105\}/16\; \backslash approx\; 2.077\backslash ldots$
10	$3\backslash sqrt\{2\}/2\; \backslash approx\; 2.121\backslash ldots$
11	2.214...
12	$\backslash sqrt\{5\}\; \backslash approx\; 2.236\backslash ldots$

---

In other shapes

Packing squares into other shapes can have high computational complexity: testing whether a given number of axis-parallel unit squares can fit into a given polygon is NP-complete. It remains NP-complete even for a simple polygon (with no holes) that is orthogonally convex, with axis-parallel sides, and with half-integer vertex coordinates.

---

See also

• Circle packing in a square
• Squaring the square
• Rectangle packing
• Moving sofa problem

---

External links

Categories: Packing Problems, Unsolved Problems In Geometry

Post Comment